package com.wangwei.basic;

import edu.princeton.cs.algs4.StdOut;

/**
 * 下压堆栈（链表实现）
 * @param <Item>
 */
public class Stack<Item> {

    private Node first;
    private int N;

    private class Node{
        Item item;
        Node next;
    }

    public boolean isEmpty(){
        return first ==null;
    }

    public int size(){
        return N;
    }

    public void push(Item item){
        Node oldFirst = first;
        first = new Node();
        first.item =item;
        first.next =oldFirst;
        N++;
    }

    public Item pop(){
        Item item = first.item;
        first = first.next;
        N--;
        return item;
    }

    public static void test(String exp){
        Stack<String> s =new Stack<>();
        String[] arr =exp.split(" ");
        for(String item : arr){
            if(!item.equals("-")){
                s.push(item);
            }else if(!s.isEmpty()){
                StdOut.println(s.pop()+"");
            }
        }
        StdOut.println("("+s.size()+" left on stack)");
    }

    public static void main(String[] args) {
        String exp="to be or not to - be - - that - - - is";
        test(exp);
    }

}